/*
 * @Author: your name
 * @Date: 2021-10-20 20:55:15
 * @LastEditTime: 2021-10-20 21:07:15
 * @LastEditors: Please set LastEditors
 * @Description: https://www.luogu.com.cn/problem/P1757
 * @FilePath: \luogu\动态规划\背包\分组背包\P1757 通天之分组背包\other.cpp
 */
#include<iostream>
#include<queue>
#include<iomanip>
#include<cstdio>
#include<algorithm>
#include<stack>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<string>
#include<map>
#include<set>

using namespace std;

int zhong[1001],jia[1001],a[1001][1001],bb[1001];//物品的重量 价值 记录分组 背包 

int main()
{
	int n,m,zu,mxzu = 0;//找一共有多少个分组 
	cin>>m>>n;
	for(int i = 1;i <= n;++ i)
	{
		cin>>zhong[i]>>jia[i]>>zu;
		a[zu][0] ++;//计数  记录该组最多能够有多少物品
		a[zu][a[zu][0]] = i;//记录下标 
		mxzu = max(mxzu,zu);//比较找最大的那个 
	}
	for(int i = 1;i <= mxzu;++ i)
		for(int j = m;j >= 0;j --)
			for(int k = 1;k <= a[i][0];++ k)
				if(j >= zhong[a[i][k]])//判断是否越界 
					bb[j] = max(bb[j],bb[j - zhong[a[i][k]]] + jia[a[i][k]]);//比较找最大的然后更新 
	printf("%d\n",bb[m]);
	return 0;
}